// https://www.lintcode.com/problem/n-queens/

public class Solution {
    /*
     * @param n: The number of queens
     * @return: All distinct solutions
     */
    public List<List<String>> solveNQueens(int n) {
        // write your code here
        List<List<String>> ret = new ArrayList<>();
        _solveNQueens(n, 0, new ArrayList<List<Integer>>(), ret);
        return ret;
    }
    
    private void _solveNQueens(int n, int row, List<List<Integer>> queens, List<List<String>> ret) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; ++j) {
                    if (j == queens.get(i).get(1)) {
                        sb.append('Q');
                    } else {
                        sb.append('.');
                    }
                }
                solution.add(sb.toString());
            }
            ret.add(solution);
        } else {
            for (int col = 0; col < n; ++col) {
                if (check(queens, row, col)) {
                    List<Integer> p = new ArrayList<>();
                    p.add(row);
                    p.add(col);
                    queens.add(p);
                    _solveNQueens(n, row + 1, queens, ret);
                    queens.remove(queens.size() - 1);
                }
            }
        }
    }
    
    private boolean check(List<List<Integer>> queens, int row, int col) {
        for (List<Integer> queen : queens) {
            int r = queen.get(0);
            int c = queen.get(1);
            if ((c == col) || (Math.abs(r - row) == Math.abs(c - col))) {
                return false;
            }
        }
        return true;
    }
}